import igraph as ig


class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 顶点数
        self.graph = [[] for _ in range(vertices)]  # 邻接表
        self.time = 0

    # 添加边
    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    # 查找所有 2-node 或更大割集的递归函数
    def _find_critical_nodes(self, u, visited, parent, disc, low, cut_sets, stack):
        children = 0
        visited[u] = True
        disc[u] = low[u] = self.time
        self.time += 1
        stack.append(u)

        # 遍历邻居节点
        for v in self.graph[u]:
            if not visited[v]:
                parent[v] = u
                children += 1
                self._find_critical_nodes(v, visited, parent, disc, low, cut_sets, stack)

                # 检查子树是否有连接到祖先的反向边
                low[u] = min(low[u], low[v])

                # 如果子树没有连接到祖先的反向边
                if parent[u] is None and children > 1:
                    # 如果 u 是根节点，且有两个或更多子节点，保存它作为一个割集
                    cut_sets.append(u)

                if parent[u] is not None and low[v] >= disc[u]:
                    cut_sets.append(u)

            elif v != parent[u]:  # 反向边
                low[u] = min(low[u], disc[v])

        # 如果当前节点是根节点且 children > 1，保存节点作为割点
        if parent[u] is None and children > 1:
            cut_sets.append(u)

    # 查找割集
    def find_critical_nodes(self):
        visited = [False] * self.V
        disc = [-1] * self.V  # 发现时间
        low = [-1] * self.V  # 最低可到达节点
        parent = [None] * self.V  # 父节点
        cut_sets = []  # 保存割集
        stack = []  # 保存当前路径

        # 遍历所有节点
        for i in range(self.V):
            if not visited[i]:
                self._find_critical_nodes(i, visited, parent, disc, low, cut_sets, stack)

        # 找出至少两个节点才能分割的集合
        return set(cut_sets)


# 示例图
g = Graph(7)
edges = [(0, 1), (0, 5), (0, 6), (3, 6), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (5, 6)]
for i, j in edges:
    g.add_edge(i, j)
# 查找割集
critical_nodes = g.find_critical_nodes()
print("删除两个或更多节点才能改变连通性的节点集合:", critical_nodes)

g = ig.Graph(7, edges)
ncs = g.minimum_size_separators()
print(f"所有的节点割集为:{ncs}")

k = g.vertex_connectivity()
print(f"图的节点连通度为{k}")

# 枚举所有可能的节点对，计算s-t最小割集
min_cuts = []
for i in range(g.vcount()):
    for j in range(i + 1, g.vcount()):
        # 找到节点i和j之间的最小割集
        cut = g.st_mincut(i, j)
        if cut:
            min_cuts.append((i, j, cut))

# 输出所有最小节点切割集
for s, t, cut in min_cuts:
    print(f"Minimum cut between {s} and {t}: {cut}")
